package sort;

public class QuickSort {
    public static void quick(int[] array){
        quickPartition(array,0,array.length-1);
    }

    private static void quickPartition(int[] array,int from,int to){
        if(to - from <= 0){
            return;
        }
        int pi = partitionMethod(array,from,to);
        quickPartition(array,from,pi - 1);  //处理partition左边部分
        quickPartition(array,pi + 1,to);  //处理partition右边部分
    }

    private static int partitionMethod(int[] array,int from,int to){  //[from,to]
        int pivot = array[to]; //初始分割点
        int left = from;
        int right = to;
        while(left < right){
            while(left < right && array[left] <= pivot){
                left++;
            }
            //while循环结束后得到的是大于pivot的部分
            while(left < right && array[right] >= pivot){ //得到从右边开始小于pivot的元素
                right--;
            }
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
        }
        int tmp = array[to];
        array[to] = array[left];
        array[left] =   tmp;
        return left;
    }

}
